1. Field of the Invention
The invention relates to methods for protecting cryptographic devices against side channel attacks, and to cryptographic devices embedding such methods.
2. Description of the Related Art
As known in the art, cryptographic devices are devices implementing cryptographic mechanisms. Examples of cryptographic devices include smart cards, USB keys, dongles, Personal Digital Assistants (a.k.a PDAs), mobile phones, personal computers (a.k.a PCs), etc. Such cryptographic devices are used in particular for securing a user's electronic transactions. The expression “electronic transaction” is to be taken in its broadest meaning. I.E. it is not limited to financial transaction but also contain any Internet transaction, any transaction occurring through a telecommunication network etc. Securing electronic transactions may comprise the cryptographic mechanisms of digitally signing electronic documents, decrypting electronic documents, negotiating session keys with a third party and/or authenticating a user. The above four cryptographic mechanisms are well known in the art. They are not limitative (other cryptographic mechanisms exist), and not mandatory (for example a cryptographic device does not necessarily embed a digital signature mechanism).
Cryptographic mechanisms have an input and an output. For example, an encryption mechanism may have an input consisting of a plaintext and an output consisting of a ciphertext. When first cryptographic devices were designed, people had the feeling that the only attacks possible on their cryptographic mechanisms consisted in attacking the input and output. However, it turned out that cryptographic devices are also susceptible to so-called “side channel attacks”. Side channel attacks rely on the fact that a cryptographic device has input and output means other than the legitimate input and output means. For example use of illegitimate, input means may comprise altering cryptographic operations by heating the cryptographic device, by modifying its clock (e.g. speeding up above the recommended limit), by putting it under UV light, X-Ray, or ultrasonic waves, by shaking it or otherwise mechanically acting on it, etc. Such alteration can be carefully designed (for example a glitch can be introduced at the exact moment that a counter is about to be decremented) or can be random (for example the aim might simply be to induce a random fault and analyze the consequence of the fault, which may leak sensitive information). Use of illegitimate output means may comprise analyzing the power consumption of the cryptographic device (e.g. an electronic component requires more electric power to perform a complex operation such as “square and multiply” than it does for a simple operation such as “square only”), analyzing the electromagnetic field created by the cryptographic device, analyzing the sounds emitted by the cryptographic device, etc. Well-known side channel attacks include Simple Power Analysis (SPA), Differential Power Analysis (DPA) or Differential Fault Analysis (DFA).
Cryptographic mechanisms consist of mechanisms involving at least a secret D which is supposed to be stored securely in a cryptographic device. D should not be leaked outside the cryptographic device through any attack. In a manner known in the art, D can be represented in the form of an n-bit number (d0, d1, . . . dn−1)2, where di is a bit (for each integer i between 0 and n−1). In the rest of the document, the exponent D will be denoted {d0, d1, . . . dn−1}2 instead of (d0, d1, . . . dn−1)2 as is usually the case in mathematics in order not to introduce any ambiguity with the reference signs placed in the claims between parentheses as per the European Patent Convention.
In abstract algebra, which is a branch of mathematics, a monoid (M, ⊥) is defined as an algebraic set, the set being closed under an associative binary operation ⊥, the set having an identity element. Contrary to a group, in a monoid every element does not necessarily have an inverse. The operation ⊥ can also be represented with other symbols. For example, the operation ⊥ can be represented as an additive operation (symbol +), as a multiplicative operation (symbol *), etc. This representation is purely formal and does not affect the properties of the monoid. In the rest of the application, monoids will be represented with the multiplicative operation *, and will be denoted {M, *} instead of (M, *) in order not to introduce any ambiguity with the reference signs placed in the claims between parentheses as per the European Patent Convention.
Monoids are widespread in cryptography. The most widespread monoids in the field of cryptography are large monoids having many invertible elements, e.g. 280 invertible elements. For example, with the RSA algorithm, almost all elements are invertible (the exceptions being in particular the multiples of p and q). M* denotes the set containing all invertible elements of the set M of the monoid {M, *}.
In the rest of the application, all monoids are abelian monoids, that is monoids in which all elements commute.
Cryptographic mechanisms particularly sensitive to side channel attacks comprise mechanisms in which for each di equal to a certain value v (i.e. v=0 or v=1), the mechanism calculates X2 and Y*Z (where X, Y and Z are three elements of a monoid {M, *}), and for each dj equal to the other value (dj=1−v), the mechanism calculates T2 (where T is an element of the monoid {M, *}). Examples of such mechanisms include RSA modular exponentiation.
X2 is called a squaring operation and stands for X*X.
Xn stands for X*X* . . . *X where X appears n times.
Note: in a monoid with an additive notation, X2 would be written 2X and would stand for X+X. Similarly, Xn would be written nX and would stand for X+X+ . . . +X where X appears n times.
Y*Z is called a multiplication operation.
The invention improves the resistance of above-mentioned particularly sensitive cryptographic mechanisms to side channel attacks. Examples of such mechanisms include elliptic curve point multiplications, and modular exponentiations used when performing an RSA operation or a Diffie Hellman key establishment. The invention also limits the amount of processing required for securing the cryptographic mechanisms. It does so by introducing a particular type of masking mechanism (also known as blinding mechanism).